package hihocode;

import java.util.Random;
import java.util.Scanner;

public class RemoveChars {

	private static String lastString;

	private static Random random = new Random();
	
	//随机的测试用例
	public static void main2(String[] args) {
		int i = random.nextInt(100);
		int testCase = random.nextInt(1000);
		StringBuilder sb = new StringBuilder();
		for (int j = 0; j < testCase; j++) {
			for (int k = 0; k < i; k++) {
				int m = random.nextInt(3);
				sb.append((char)('A' + m));
			}
			String string = sb.toString();
			int res1 = pa(string);
			int res2 = getValue(string);
			if(res1 != res2){
				System.out.println("res1 " + res1 + " res2 " + res2);
				System.out.println(string);
				break;
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int count = scanner.nextInt();
		scanner.nextLine();
		String string;
		// 先消除，然后求剩余字符串的最长回文子串。结果 = 消除的长度 + 回文长度 + 1
		// 因为回文一定是奇数回文，偶数回文会消除
		// 比如ABABCBABA
		// 那么我们先在中间插入C，之后就会发现可以将该回文子串给消除了
		// 所以还可以消除的长度是回文子串的长度+插入字符的长度
		//最后证明，这种思路是错的
		//反例如下
		//BBABCBCCABCCCABCCBCABBBABAAABBBABCBCCBCCCABAABAABCCCBBCABCABAABCACCBCBCBCABC
		for (int i = 0; i < count; i++) {
			string = scanner.nextLine();
			int remove = removeChar(string);
			System.out.println("remove count: " + remove);
			System.out.println("lastString" + lastString);
			int palidromeLength = longestPalindromeManacher(lastString);
			System.out.println("palidromeLength: " + palidromeLength);
			System.out.println(remove + palidromeLength + 1);
			
			System.out.println("correct: " + getValue(string));
		}
		scanner.close();
	}
	
	public static int pa(String string){
		int remove = removeChar(string);
		int palidromeLength = longestPalindromeManacher(lastString);
		return remove + palidromeLength + 1;
	}
	

	public static int removeChar(String string) {
		if (string.equals("")) {
			lastString = "";
			return 0;
		}
//		int res = 0;
		StringBuilder sb = new StringBuilder();
		int length = string.length();
		int index = 1;
		// 用来表示最后是否是重复元素结尾
		boolean flag = false;
		int removeCount = 0;
		while (index < length) {
			if (string.charAt(index - 1) != string.charAt(index)) {
				sb.append(string.charAt(index - 1));
			} else {
				while (index < length
						&& string.charAt(index - 1) == string.charAt(index)) {
					if (index == length - 1) {
						flag = true;
					}
					index++;
					// 此时res只是表示找到几个相同的字符对
					// 比如CCC，res会为2
//					res++;
				}
			}
//			// 加1之后表示移除的字符数
			//傻逼了，直接将string的长度减去sb的长度就好了啊
//			if (res != 0) {
//				removeCount += ++res;
//				res = 0;
//			}
			index++;
		}
		if (!flag) {
			sb.append(string.charAt(length - 1));
		}
		removeCount = length - sb.length();
		System.out.println("after remove duplicate: " + sb + " removeCount " + removeCount);
		// 此时没有可以消除的
		if (removeCount == 0) {
			lastString = sb.toString();
			return removeCount;
		}
		int next = removeChar(sb.toString());
		return removeCount + next;
	}
	
	// 令f[i] 表示以第i个字符为中心的最长回文子串的长度
	// 通过使得右边界（j + f(j) / 2）最大的那个j来辅助计算
	// 所以公式将变成 f(i) ≥ min{f(2 * j - i) , f(j) - 2*(i - j)}这种形式了！

	// 统计使得回文串右边界（j + f(j) / 2）最大的那个j，
	// 然后再计算每一个i的时候，都可以通过f(i)≥ min⁡{f(2*j-i), f(j)-2*(i-j)}这个公式来知道f(i)的一个最小值
	// 这样避免很多不必要的运算
	public static int longestPalindromeManacher(String s) {
		if (s == null) {
			return 0;
		}
		s = new StringBuilder(s).insert(0, '^').append('&').toString();
		//System.out.println("after process:" + s);
		// 因为我们能够保证总是奇数回文串
		int len = s.length();

		// P数组存放在以index为中心的回文长度
		int[] length = new int[len];
		int C = 0, R = 0; // C为最长回文子串的中心位置，R为当前最长回文子串的右边界位置
		// 第0个字符和最后一个字符是无效字符，仅为了避免边界检查
		for (int i = 1; i < len - 1; i++) {
			// 计算i以C为中心的对应回文左边匹配位置
			// C 等于上一轮的j
			int iMirror = 2 * C - i;

			// R > i 表示i...R是回文串的右半部分
			// 初始iMirror为-1，但是此时R < i
			// R为f(j) / 2 + C
			// 那这个为什么不是f(j) + 2 * C - 2 * i呢
			length[i] = (R > i) ? Math.min(2 * R + 1 - 2 * i, length[iMirror]) : 1;

			// 贪心拓展以i为回文中心的回文子串
			while (s.charAt(i + length[i] / 2 + 1) == s.charAt(i - length[i] / 2 - 1)) {
				length[i] += 2;
			}

			// 如果以i为中心的回文扩展超过了R，则我们找到一个新的更长回文子串
			// 因此 更新 最长回文子串的中心和右边界
			if (length[i] / 2 > R - i) {
				C = i;
				R = i + length[i] / 2;
			}
		}

		// 现在P[i]数组里存放了以i为中心的回文子串长度，用打擂台方式找到最长者
		int maxLen = 0;
		String value = "";
		for (int i = 1; i < len - 1; i++) {
			if (length[i] > maxLen) {
				value = s.substring(i - length[i] / 2, i + length[i] / 2 + 1);
				maxLen = length[i];
			}
		}
		System.out.println("logest Palidrome: " + value);
		return maxLen;
	}
	
    public static int getValue(String string) {
		StringBuffer buffer = new StringBuffer(string);
		int min = buffer.length();
		for (int j = 0; j < buffer.length(); j++) {
			for (char ch = 'A'; ch <= 'C'; ch++) {
				StringBuffer temp = new StringBuffer(buffer);
				temp = temp.insert(j, ch);
				int count = handle(temp);
				if(count < min){
					System.out.println("the last insert:" + j);
					System.out.println("correct" + temp);
					min = count;
				}
//				min = min > count ? count : min;
			}
		}
		return buffer.length() + 1 - min;
    }
    
    public static int handle(StringBuffer buffer) {
        int count = 0;
        while (true) {
            StringBuffer temp = new StringBuffer();
            int i = 0, j = 1;
            for (; j < buffer.length(); j++) {
                if (buffer.charAt(i) != buffer.charAt(j)) {
                    temp.append(buffer.charAt(i));
                } else {
                    while (j < buffer.length()
                            && buffer.charAt(i) == buffer.charAt(j))
                        j++;
                }
                i = j;
            }
            if (j == buffer.length()) {
                temp.append(buffer.charAt(i));
            }
            if (temp.length() == buffer.length()) {
                count = temp.length();
                break;
            }
            buffer = temp;
        }
        return count;
    }
}
